Known as a method allowing a target encrypted, piece of information to be retrieved from pieces of encrypted information is a method of appending additional information for retrieval (a tag) to each of the pieces of encrypted information. By generating a tag from, a keyword used by a user to retrieve a piece of information, this method allows the piece of encrypted information appended with a tag that matches the generated tag to be acquired. In this manner, target information can be retrieved without decoding the encrypted information.
If the target information is retrieved frequently, however, the security may deteriorate, because frequent retrieval may permit the content of the plaintext, to be inferred from the tags, or may lead to the leakage of information such as the retrieval frequencies of the plaintext. To improve the security of such a method, it is necessary to increase the size of the encryption key size and the tag size. When the encryption key size and the tag size are increased, however, the amount of information required for a retriever to own in order to retrieve a piece of information is increased as well.